package com.github.yangyishe.p100;

import java.util.*;

/**
 * 97. 交错字符串
 * https://leetcode.cn/problems/interleaving-string/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 *
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 *
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1   ------------这个条件实际是多余的
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 注意：a + b 意味着字符串 a 和 b 连接。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出：true
 * 示例 2：
 *
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出：false
 * 示例 3：
 *
 * 输入：s1 = "", s2 = "", s3 = ""
 * 输出：true
 *
 *
 * 提示：
 *
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 *
 *
 * 进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?
 */
public class Problem97 {
    public static void main(String[] args) {
        String s1="aabcc";
        String s2="dbbca";
        String s3="aadbbbaccc";

        Problem97 problem97 = new Problem97();
        boolean interleave = problem97.isInterleave(s1, s2, s3);
        System.out.println("interleave = " + interleave);
    }

    /**
     * 思路1:
     * 在s1和s2处, 分别创建两个指针p1和p2
     * 之后再遍历s3时, 分别从p1和p2处获取字符, 只要一个地方能够获取, 就跳转即可
     * 如果遇到字符都不匹配的情况, 就说明false, 否则就说明true
     *
     * 测试实例:
     * s1: aabcd
     * s2: aefgh
     * s3: aefghaabcd
     *
     * 如果按照思路1, 先判定s1之后, 再找e的时候都找不到, 就会false了, 然而实际是true的
     * 即: error
     *
     * 思路2:
     * 使用递归回溯的方式, 如果有两个选择都可以的情况下, 各自调用. 最后只要有一个成功即是成功
     * 该思路可行, 但在以下测试实例中超出时间了.
     *
     * 测试示例2:
     * s1: abababababababababababababababababababababababababababababababababababababababababababababababababbb
     * s2: babababababababababababababababababababababababababababababababababababababababababababababababaaaba
     * s3: abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababbb
     *
     * 即: correct but too slow
     *
     * 思路3:
     * 思路2的本质, 是一种深度优先的判断.
     * 可以换一种广度优先的判断.
     * 创建一个三维数组.
     * 第一维与s3的长度相等, 记录由s1和s3构建的可能组合的集合
     * 第二维即可能组合的集合, 至少应有1个, 否则返回false
     * 第三维分别记录s1和s2的下标
     *
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()){
            return false;
        }
        if(s1.length()==0){
            return s2.equals(s3);
        }
        if (s2.length()==0) {
            return s1.equals(s3);
        }
        if(s3.length()==0){
            return true;
        }
        //1. 动态规划数组创建
        int[][][] results=new int[s3.length()][][];

        //2. 初始化
        List<int[]> first=new ArrayList<>();
        if(s1.charAt(0)==s3.charAt(0)){
            first.add(new int[]{1,0});
        }
        if(s2.charAt(0)==s3.charAt(0)){
            first.add(new int[]{0,1});
        }
        results[0]=first.toArray(new int[][]{});

        //3. 遍历推进
        for(int i=1;i<s3.length();i++){
            int[][] tempArr=results[i-1];
            List<int[]> midPass=new ArrayList<>();
            for (int[] temp : tempArr) {
                if (temp[0]<s1.length()&&s1.charAt(temp[0])==s3.charAt(i)) {
                    midPass.add(new int[]{temp[0]+1,temp[1]});
                }
                if(temp[1]<s2.length()&&s2.charAt(temp[1])==s3.charAt(i)){
                    midPass.add(new int[]{temp[0],temp[1]+1});
                }
            }

            if(midPass.isEmpty()){
                return false;
            }
            // 应该增加去重环节
            Map<Integer,Integer> indexMap=new HashMap<>();
            for (int[] pass : midPass) {
                indexMap.put(pass[0],pass[1]);
            }
            results[i]=new int[indexMap.size()][2];
            int itr=0;
            for(Map.Entry<Integer,Integer> entry:indexMap.entrySet()){
                results[i][itr++]=new int[]{entry.getKey(),entry.getValue()};
            }

        }

        //4. 返回

        return results[s3.length()-1].length>0;
    }

    /*public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()){
            return false;
        }
        return search(s1,s2,s3,0,0,0);
    }

    private boolean search(String s1,String s2,String s3,int p1,int p2,int p3){

        if(p3==s3.length()){
            return true;
        }
        if(p1<s1.length()&&s1.charAt(p1)==s3.charAt(p3)){
            boolean search = search(s1, s2, s3, p1 + 1, p2, p3 + 1);
            if (search) {
                return true;
            }
        }
        if(p2<s2.length()&&s2.charAt(p2)==s3.charAt(p3)){
            boolean search = search(s1, s2, s3, p1, p2 + 1, p3 + 1);
            if (search) {
                return true;
            }
        }
        return false;
    }*/
}
